|
1. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
提示：
树中节点的数目在范围 [0, 5000] 内
-1000
//先序遍历
if(root==null){
return false;
}
else{
return searchTarget(root,targetSum);
}
}
public boolean searchTarget(TreeNode root,int targetSum){
if(root!=null){
targetSum-=root.val;
if(root.left==null&&root.right==null){
if(targetSum==0){
return true;
}
}
return searchTarget(root.left,targetSum)||searchTarget(root.right,targetSum);
}
return false;
}
}
2. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示：
树中节点总数在范围 [0, 5000] 内
-1000
List list=new ArrayList();
calPath(root,targetSum,list);
return result;
}
public List copy(List One){
List list=new ArrayList();
for(Integer x:One){
list.add(x);
}
return list;
}
public void calPath(TreeNode root,int targetSum,List list){
if(root!=null){
list.add(root.val);
targetSum-=root.val;
if(root.left==null&&root.right==null){
if(targetSum==0){
result.add(copy(list));
}
list.remove(list.size()-1);
}
else{
calPath(root.left,targetSum,list);
calPath(root.right,targetSum,list);
list.remove(list.size()-1);
}
}
}
}
3. 路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
本题是一个双重递归，需要特别注意的就是结点的值有正有负这跟之前全为正数有一个特别大的差别就是必须遍历到每个分支的叶子结点才能够找全路径数目！
class Solution {
int num=0;
public int pathSum(TreeNode root, int targetSum){
num=calPathSum(root,targetSum);
return num;
}
public int judge(TreeNode root,int targetSum,int nowSum){
//判断从root结点出发是否有存在路径值=targetSum的路径。
if(root!=null){
nowSum+=root.val;
if(nowSum==targetSum){
return 1+judge(root.right,targetSum,nowSum)+judge(root.left,targetSum,nowSum);
}
else{
return judge(root.right,targetSum,nowSum)+judge(root.left,targetSum,nowSum);
}
}
else{
return 0;
}
}
public int calPathSum(TreeNode root,int targetSum){
if(root!=null){
return calPathSum(root.left,targetSum)+calPathSum(root.right,targetSum)+judge(root,targetSum,0);
}
else{
return 0;
}
}
}
|